//
// Created by 86136 on 2024/11/23.
//

# pragma once
#include <iostream>
#include <mutex>

// 封装了malloc和free操作，可以设置OOM释放内存的回调函数
template <int __inst>
class __malloc_alloc_template {
private:
    static void* _S_oom_malloc(size_t);
    static void* _S_oom_realloc(void*, size_t);
    static void (* __malloc_alloc_oom_handler)();

public:
    static void* allocate(size_t __n)
    {
        void* __result = malloc(__n);
        if (0 == __result) __result = _S_oom_malloc(__n);
        return __result;
    }

    static void deallocate(void* __p, size_t /* __n */)
    {
        free(__p);
    }

    static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
    {
        void* __result = realloc(__p, __new_sz);
        if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
        return __result;
    }

    static void (* __set_malloc_handler(void (*__f)()))()
    {
        void (* __old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = __f;
        return(__old);
    }

};

template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = nullptr;

template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        if (nullptr == __my_malloc_handler) { throw std::bad_alloc(); }
        (*__my_malloc_handler)();
        __result = malloc(__n);
        if (__result) return(__result);
    }
}

template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        if (nullptr == __my_malloc_handler) { throw std::bad_alloc(); }
        (*__my_malloc_handler)();
        __result = realloc(__p, __n);
        if (__result) return(__result);
    }
}

/*
 * 移植SGI STL二级空间配置器源码 模板实现
 * 考虑多线程线程安全的问题
 * 在nginx中 一个线程可以创建一个独立的nginx内存池来使用 不用关心线程安全问题
 * 在SGI STL中，容器产生的对象是很有可能在多个线程中去操作的
 */

template<typename T>
class myallocator {
public:
    using value_type = T;

    constexpr myallocator() noexcept {}

    constexpr myallocator(const myallocator&) noexcept = default;

    template<class _Other>
    constexpr myallocator(const myallocator<_Other>&) noexcept {

    }

    // 开辟内存
    T* allocate(size_t __n) {
        void* __ret = 0;

        if (__n > (size_t) _MAX_BYTES) {
            // 申请的空间大于_MAX_BYTES，则不由内存池管理，调用malloc_alloc::allocate分配空间，底层就是malloc
            __ret = malloc(__n);
        }
        else {
            // __my_free_list 指向__n个字节应该在内存池哪个块分配
            _Obj* volatile* __my_free_list = _S_free_list + _S_freelist_index(__n);

            // 加锁，出作用域自动析构
            std::lock_guard<std::mutex> guard(mtx);

            // __result指向待分配内存的链表，准备在__result 下分配内存
            _Obj* __result = *__my_free_list;
            if (__result == 0)
                // 若__result下没有挂着空闲的chunk块，_S_refill直接构造chunk后分配，_S_round_up(__n)指的是内存池每个块的大小
                __ret = _S_refill(_S_round_up(__n));
            else {
                // 把_M_free_list_link理解成next，__my_free_list指向下一个节点，也就是_S_free_list的元素直接指向后面的节点
                *__my_free_list = __result -> _M_free_list_link;
                // 这时候是要把__result分配出去
                __ret = __result;
            }
        }
        return (T*)__ret;
    }

    // 释放内存
    void deallocate(void* __p, size_t __n) {
        if (__n > (size_t) _MAX_BYTES)
            free(__p);
        else {
            // _S_freelist_index(__n):获取__n字节在_S_free_list中哪个小的内存池分配的
            // __my_free_list 指向小内存池的起始地址
            _Obj* volatile*  __my_free_list = _S_free_list + _S_freelist_index(__n);
            // __q指向要归还的__chunk块
            _Obj* __q = (_Obj*)__p;

            // 加锁，出作用域自动析构
            std::lock_guard<std::mutex> guard(mtx);
            // 即将归还__chunk块的next被赋值成当前还未分配出去__chunk块的首地址
            __q -> _M_free_list_link = *__my_free_list;
            // 修改_S_free_list的元素，即修改了当前还未分配出去__chunk块的首地址
            *__my_free_list = __q;
        }
    }

    // 内存扩容 or 缩容
    void* reallocate(void* __p, size_t __old_sz, size_t __new_sz) {
        // 参数:chunk块的其实地址、调整前chunk块的大小、调整后chunk块的大小
        void* __result;
        size_t __copy_sz;

        if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
            // __old_sz和__new_sz都大于128字节，并不是从内存池分配的内存，直接调用库函数realloc
            return(realloc(__p, __new_sz));
        }
        // __old_sz和__new_sz处于同一数量区间，不用扩容或缩容
        if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
        // __result指向重新分配的空间
        __result = allocate(__new_sz);
        // __copy_sz 保存最小值
        __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
        // 从__p拷贝到__result，扩容拷贝__old_sz字节，缩容拷贝__new_sz
        memcpy(__result, __p, __copy_sz);
        // 归还原来的chunk块到内存池
        deallocate(__p, __old_sz);
        return(__result);
    }

    // 对象构造
    void construct(T* __p, const T &val) {
        new (__p) T(val);
    }

    // 对象析构
    void construct(T* __p) {
        __p->~T();
    }
private:
    // 对齐字节数
    enum {_ALIGN = 8};
    // 数组对应位置挂的内存池最大的__chunk块的的大小为128B，即freelist有16个元素
    //如果大于128字节就相当于是大块内存，不通过内存池管理，还是用malloc、free管理
    enum {_MAX_BYTES = 128};
    // 自由链表中Obj*的个数
    enum {_NFREELISTS = 16};

    // 每一个chunk块的头信息
    union _Obj {
        union _Obj* _M_free_list_link;     // 指向下一个空闲chunk块的起始地址
        char _M_client_data[1];
    };

    // 记录内存块的分配状态，Chunk allocation state.
    // 全部会初始化为0
    static char* _S_start_free;     // 备用内存空间的开始位置
    static char* _S_end_free;       // 备用内存空间的结束位置
    static size_t _S_heap_size;     // 向OS申请的所有内存大小

    // 多线程环境中，堆或者数据段的数据都会加上__STL_VOLATILE，防止各个线程对数据进行缓存
    static _Obj* volatile _S_free_list[_NFREELISTS]; // 会初始化为0

    // 内存池基于freelist实现，需要考虑线程安全
    static std::mutex mtx;

    // 容器空间配置器申请内存的时候，会用_S_round_up把所申请的字节__bytes大小上调至8的整数倍
    static size_t _S_round_up(size_t __bytes) {
        return (((__bytes) + (size_t) _ALIGN - 1) & ~((size_t) _ALIGN - 1));
    }

    static size_t _S_freelist_index(size_t __bytes) {
        return (( (__bytes) + (size_t)_ALIGN-1) / (size_t)_ALIGN - 1);
    }

    // 把分配好的chunk块进行连接
    static void* _S_refill(size_t __n){
        int __nobjs = 20;                             // 局部变量，内存池中开辟__chunk 块的数量
        // 申请__nobjs个__n字节chunk的空间，__nobjs按引用传入_S_chunk_alloc，__nobjs可能会在_S_chunk_alloc里被修改
        // 如果_S_start_free和_S_end_free之间的备用内存不够分配20个__n字节的chunk时，会修改__nobjs
        char* __chunk = _S_chunk_alloc(__n, __nobjs);
        _Obj* volatile* __my_free_list;         // 二级指针，遍历_S_free_list数组
        _Obj* __result;
        _Obj* __current_obj;
        _Obj* __next_obj;
        int __i;

        // 当内存池最多只能包含1个__n字节chunk块的时候，直接返回，不需要进入for循环再填写next域
        if (1 == __nobjs) return(__chunk);
        // _S_freelist_index(__n)返回的是分配的__n字节在_S_free_list的哪个元素中分配
        // __my_free_list 指向分配__n字节的元素
        __my_free_list = _S_free_list + _S_freelist_index(__n);

        /* Build free list in chunk */
        // 指向待分配出去的内存块
        __result = (_Obj*)__chunk;

        // __chunk 是char*，实际上+__n就是越过了一个__chunk块，指向了第二个__chunk 块的起始地址
        // __next_obj 和*__my_free_list 都指向第二个块
        *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);

        // i从1开始，表示__current_obj 一开始就指向第二个__chunk块
        // 整个for循环做的就是把内存是填写剩下所有__chunk块的next域
        for (__i = 1; ; __i++) {
            __current_obj = __next_obj;
            __next_obj = (_Obj*)((char*)__next_obj + __n);
            if (__nobjs - 1 == __i) {
                // next域填写完成，最后一个__chunk块的next域为0地址
                __current_obj -> _M_free_list_link = 0;
                break;
            } else {
                __current_obj -> _M_free_list_link = __next_obj;
            }
        }
        return(__result);
    }

    static char* _S_chunk_alloc(size_t __size, int& __nobjs)  // 按引用接收__nobjs
    {
        char* __result;
        // 实际分配的字节数，8 * 20
        size_t __total_bytes = __size * __nobjs;
        //_S_end_free、_S_start_free都是static char*变量，标识备用内存池的范围，初始值为0
        // _S_start_free、_S_end_free分别记录内存池（__size * __nobjs）可用的起始和末尾地址
        size_t __bytes_left = _S_end_free - _S_start_free;

        if (__bytes_left >= __total_bytes) {
            // 正常的__size在对应的内存池分配，备用的内存池还可以继续分配__size * __nobjs
            // 可以分配出去一个小的内存池
            __result = _S_start_free;
            // 修改_S_start_free，分配__total_bytes空间出去
            _S_start_free += __total_bytes;
            return(__result);
        } else if (__bytes_left >= __size) {
            // 注意这里为什么是大于等于一个chunk块的大小__size，因为容器申请只是申请一个内存块
            // 而是空间配置器程序调用_S_chunk_alloc希望能够分配20个chunk块的内存，可以不满足分配20个块的要求，但必须满足容器申请1个内存块的要求，所以可以修改__nobjs的值
            // 假设我们向内存池申请16字节的时候，我们在_S_free_list向OS申请8字节时备用的内存池进行申请
            // 此时会进入else if

            // 剩余的字节数还能分配出__nobjs个完整的__size的__chunk块
            __nobjs = (int)(__bytes_left/__size);
            // 现在的__total_bytes 肯定不大于 _S_end_free - _S_start_free
            __total_bytes = __size * __nobjs;
            // __result 指向空闲内存池的首地址，也就是即将被分配出去的首地址
            __result = _S_start_free;
            // 更新空闲内存池的首地址
            _S_start_free += __total_bytes;
            return(__result);
        } else {
            // 没有足够的空间分配了 或者_S_free_list还没有申请过内存池 ，需要申请内存
            // _S_heap_size初始值为0，第一次向OS申请的话__bytes_to_get = 2 * 8 * 20 = 320
            // _S_heap_size记录了已经向OS申请的所有空间
            size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
            // Try to make use of the left-over piece.
            if (__bytes_left > 0) {
                // 由于之前申请的备用内存太小，甚至无法分出一个size
                // 这里剩余的内存必然为8的整数倍，且在区间[8,128)内。因为从OS申请空间的时候就是按照8的整数申请的
                // 之前申请的备用内存，会被挂在__my_free_list后，专门用于分配指定大小的内存
                // 而且只能分配 <指定大小的内存> 一次
                _Obj* volatile* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);
                //
                ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
                *__my_free_list = (_Obj*)_S_start_free;
            }
            // 用malloc申请__bytes_to_get个字节，也就是一个小的内存池了，_S_start_free 指向小内存池的首地址
            _S_start_free = (char*)malloc(__bytes_to_get);
            if (nullptr == _S_start_free) {
                // 向OS申请内存失败
                size_t __i;
                _Obj* volatile* __my_free_list;
                _Obj* __p;
                // Try to make do with what we have.  That can't
                // hurt.  We do not try smaller requests, since that tends
                // to result in disaster on multi-process machines.
                // 1. 剩余的备用内存连一个__size的空间都不够，2. 向OS申请__bytes_to_get字节内存失败
                // 从__size开始在_S_free_list中从前往后找
                for (__i = __size; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) {
                    __my_free_list = _S_free_list + _S_freelist_index(__i);
                    __p = *__my_free_list;
                    if (0 != __p) {
                        // 找到_S_free_list中已经分配内存池的位置
                        // 修改_S_free_list的对应位置的地址，准备分配出一整个__i块出去
                        *__my_free_list = __p -> _M_free_list_link;
                        // 在_S_free_list别的地方拿到未分配的内存块后，修改_S_start_free、_S_end_free
                        // 得到新的备用内存，重新给用户分配__nobjs个__size的空间
                        _S_start_free = (char*)__p;
                        _S_end_free = _S_start_free + __i;
                        return(_S_chunk_alloc(__size, __nobjs));
                        // Any leftover piece will eventually make it to the right free list.
                    }
                }
                // 若for循环完成，依然找不到空闲的内存块
                _S_end_free = nullptr;	// In case of exception.
                // 重新再次申请__bytes_to_get字节
                _S_start_free = (char*)malloc(__bytes_to_get);
            }
            // _S_heap_size 记录所有申请的堆空间大小
            _S_heap_size += __bytes_to_get;
            // _S_end_free 指向空闲小内存池的尾地址
            _S_end_free = _S_start_free + __bytes_to_get;
            return(_S_chunk_alloc(__size, __nobjs));
        }
    }


};

// 类外初始化静态成员变量
template <typename T>
char* myallocator<T>::_S_start_free = nullptr;

template <typename T>
char* myallocator<T>::_S_end_free = nullptr;

template <typename T>
size_t myallocator<T>::_S_heap_size = 0;

template <typename T>
typename myallocator<T>::_Obj* volatile myallocator<T>::_S_free_list[_NFREELISTS] = {nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};

template <typename T>
std::mutex myallocator<T>::mtx;





